﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

// 1. Initialize each element as a cluster
// 2. Calculate the distances of all clusters to all other clusters
// 3. Merge clusters to new clusters and recalculate distances in a loop until there are only countCluster clusters
namespace HAC
{
    public class HAC
    {
        HashSet<Element> elements = new HashSet<Element>();
        Dictionary<string, Cluster> elementID_Cluster_Map = new Dictionary<string, Cluster>();
        ClusterPairs pairs = new ClusterPairs();
        Fusion fusion;
        IDistanceMetric metric;

        private HashSet<Cluster> clusters = new HashSet<Cluster>();

        public static HashSet<int> validClusterIDs = new HashSet<int>();

        public static int ClusterCountAccumulator = 0;
        
        public static Dictionary<int, HashSet<int>> clusterAndRelatedClustersMap = new Dictionary<int, HashSet<int>>();

        public static Dictionary<int, Cluster> cluster_map = new Dictionary<int, Cluster>();

                public HAC(HashSet<Element> elements, Fusion fusion, IDistanceMetric metric)
        {
            this.elements = elements;
            this.fusion = fusion;
            this.metric = metric;
        }

        public HAC(Fusion fusion, IDistanceMetric metric)
        {
            this.fusion = fusion;
            this.metric = metric;
            this.fusion.Metric = metric;
        }

        public void addElementPair(Element ele1, Element ele2)
        {
            Cluster cluster1 = addNewElement(ele1);
            Cluster cluster2 = addNewElement(ele2);

            //In first round, only calculate similarity between the input domain pairs[Step2]
            ClusterPair cluster_pair = new ClusterPair(cluster1, cluster2, cluster1.CalculateDistance(cluster2));
            pairs.AddPair(cluster_pair);
        }
        /*Add an element, meawhile, add a new cluster if the element is a new element*/
        public Cluster addNewElement(Element ele)
        {
            Cluster cluster = null;
            if(elementID_Cluster_Map.ContainsKey(ele.Id))
            {
                cluster = elementID_Cluster_Map[ele.Id];
            }else
            {
                elements.Add(ele);//add new element
                
                cluster = new Cluster(this.fusion);// add a new cluster
                cluster.AddElement(ele);
                addNewCluster(cluster);

                elementID_Cluster_Map.Add(ele.Id, cluster);//record this element
            }
            return cluster;
        }

        private Stopwatch sw = new Stopwatch();
        private void checkTimePeriod(string CheckPoint)
        {
            sw.Stop();
            Console.WriteLine("{0}:{1}ms", CheckPoint, sw.ElapsedMilliseconds);
            sw.Restart();
        }
        /*
         * countCluster: number of clusters need to be reserved
         * Max_Distance: if the minimum distance between each pair is greater than Max_Distance, then the clustering termincates immediately.
         * ShortCutDistance: Used to accelerate the process of finding minimum distance pair. If a pair in Pairs whose distance is smaller than the given ShortOutDistance, return it immediately.
         */
        public Cluster[] Cluster(int countCluster, float Max_Distance, float ShortCutDistance, int DebugOutputInterval)
        {
            if (DebugOutputInterval < 0)
            {
                DebugOutputInterval = int.MaxValue;
            }
            sw.Start();
            
            // Return if the element (cluster) count is lower than countCluster
            if (clusters.Count <= countCluster)
                return clusters.ToArray<Cluster>();

            int counter = 0;


            
            while (clusters.Count > countCluster)
            {
                if (counter++ == DebugOutputInterval)
                {
                    checkTimePeriod("");
                    Console.WriteLine("{0}", clusters.Count);
                    counter = 0;
                }
                //checkTimePeriod("Before pairs.LowestDistancePair");
                // a) Merge: Create a new cluster and add the elements of the two old clusters                
                ClusterPair lowestDistancePair = pairs.LowestDistancePair(ShortCutDistance);
                //checkTimePeriod("After pairs.LowestDistancePair");

                if (lowestDistancePair == null || lowestDistancePair.Distance >= Max_Distance)
                {
                    break;//add a new termination rule
                }

                Cluster newCluster = new Cluster(this.fusion);
                newCluster.AddElements(lowestDistancePair.Cluster1.GetElements());
                newCluster.AddElements(lowestDistancePair.Cluster2.GetElements());
                //record distance information
                newCluster.AddDistance(lowestDistancePair.Distance);//distance between the two clusters
                newCluster.AddDistances(lowestDistancePair.Cluster1.Distances);//distance information of the old cluster
                newCluster.AddDistances(lowestDistancePair.Cluster2.Distances);//distance information of the old cluster
                //checkTimePeriod("After initializing new cluster");

                // b)Remove the two old clusters from clusters
                clusters.Remove(lowestDistancePair.Cluster1);
                clusters.Remove(lowestDistancePair.Cluster2);
                validClusterIDs.Remove(lowestDistancePair.Cluster1.id);
                validClusterIDs.Remove(lowestDistancePair.Cluster2.id);
                //checkTimePeriod("After removing old cluster");

                // c) Remove the two old clusters from pairs
                pairs.RemovePairsByOldClusters(lowestDistancePair.Cluster1, lowestDistancePair.Cluster2);
                //checkTimePeriod("After removing old cluster pairs");
                
                // d) introduce new cluster pairs related to the new cluster
                recalculateClusterPair(newCluster, lowestDistancePair.Cluster1, lowestDistancePair.Cluster2);
                //checkTimePeriod("After recalculating new pair distances");
                
                // e) Add the new cluster to clusters
                addNewCluster(newCluster);
            }

            return clusters.ToArray<Cluster>();
        }

        /*Given a new cluster merged with two old clusters, only calculate its distance with the clsuters which are related to the two old clusters*/
        private void recalculateClusterPair(Cluster newCluster, Cluster oldCluster1, Cluster oldCluster2)
        {
            HashSet<int> relatedClusterOfCluster1 = clusterAndRelatedClustersMap[oldCluster1.id];
            
            if (relatedClusterOfCluster1 != null)
            {
                foreach (int relatedClusterID in relatedClusterOfCluster1)
                {
                    if (validClusterIDs.Contains(relatedClusterID))
                    {
                        //checkTimePeriod("1.Before getting a new pair");
                        Cluster relatedCluster = cluster_map[relatedClusterID];
                        ClusterPair pair = new ClusterPair(relatedCluster, newCluster, relatedCluster.CalculateDistance(newCluster));
                        //checkTimePeriod("1. After getting a new pair");
                        pairs.AddPair(pair);
                    }
                }
            }

            HashSet<int> relatedClusterOfCluster2 = clusterAndRelatedClustersMap[oldCluster2.id];
            if (relatedClusterOfCluster2 != null)
            {
                foreach (int relatedClusterID in relatedClusterOfCluster2)
                {
                    if (validClusterIDs.Contains(relatedClusterID) && !relatedClusterOfCluster1.Contains(relatedClusterID))
                    {
                        //checkTimePeriod("2.Before getting a new pair");
                        Cluster relatedCluster = cluster_map[relatedClusterID];
                        ClusterPair pair = new ClusterPair(relatedCluster, newCluster, relatedCluster.CalculateDistance(newCluster));
                        //checkTimePeriod("2. After getting a new pair");
                        pairs.AddPair(pair);
                    }
                }
            }
            clusterAndRelatedClustersMap.Remove(oldCluster1.id);
            clusterAndRelatedClustersMap.Remove(oldCluster2.id);
        }

        /*Add a new cluster*/
        private void addNewCluster(Cluster newCluster)
        {
            clusters.Add(newCluster);
            validClusterIDs.Add(newCluster.id);
            cluster_map.Add(newCluster.id, newCluster);
        }
        /**
         * update the related clusters of a given cluster
         * */
        public static void updateRelatedClustersOfOneCluster(int clusterId, int relatedClusterID)
        {
            HashSet<int> relatedClusters = null;
            if(!clusterAndRelatedClustersMap.ContainsKey(clusterId))
            {
                relatedClusters = new HashSet<int>();
                relatedClusters.Add(relatedClusterID);
                clusterAndRelatedClustersMap.Add(clusterId, relatedClusters);
            }else
            {
                relatedClusters = clusterAndRelatedClustersMap[clusterId];
                relatedClusters.Add(relatedClusterID);
            }
        }
    }
}
